// 编写程序以 x 为基准分割链表，使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x，x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可，其不需要被置于左右两部分之间。

// 示例:

// 输入: head = 3->5->8->5->10->2->1, x = 5
// 输出: 3->1->2->10->5->5->8

#include "stdc++.h"

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

/* 双指针
*/
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if (head == nullptr) {
            return nullptr;
        }
        ListNode* pre{head}; // small val
        ListNode* cur{head};
        while (cur) {
            if (cur->val < x) {
                int tmp = cur->val;
                cur->val = pre->val;
                pre->val = tmp;
                pre = pre->next;
            }
            cur = cur->next;
        }
        return head;
    }
};

/* 头插法
*/
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* cur{head};
        while (cur->next) {
            if (cur->next->val < x) {
                ListNode* tmp = cur->next;
                cur->next = tmp->next;
                tmp->next = head;
                head = tmp; // 新的头节点
                continue;
            }
            cur = cur->next;
        }
        return head;
    }
};